The present invention relates to a branch predictor for predicting the presence of a branch in a branch instruction, and more particularly to a technique which is effective when it is applied to a branch predictor making the prediction of whether or not a branch is to be taken by a conditional branch instruction with which the judgement is made as to whether or not a loop processing is to be iterated.
Recent microprocessors have remarkable improvements in speed. It is general in these microprocessors that the deep-pipeline execution or the out-of-order execution (in which the execution of a successor instruction is started without waiting for the completion of the execution of a predecessor instruction) is made or a cache memory is used. Though those techniques are effective, the performance is degraded in the following cases.
Namely, the pipeline execution and the out-of-order execution are effective in the case where a continuous train of instructions are to be executed. In many instances, however, a large penalty is imposed in the case where the continuity is destroyed owing to a conditional branch instruction. Accordingly, the performance is degraded in the case where a branch is generated by a conditional branch instruction.
As to the improvement in speed by the use of the cache memory, on the other hand, an instruction cache miss is generated in the case where the reference to an instruction included in no cache memory is made in a program. The generation of the instruction cache miss causes the degradation in speed.
For such circumstances, the possession of a mechanism for predicting whether or not a branch is to be taken by a conditional branch instruction is a primary issue of late. Especially, a method disclosed in the article by Tse-Yu Yeh and Yale N. Patt, "Two-Level Adaptive Training Branch Prediction", Proceedings of the 24th Annual International Symposium on Microarchitecture, 1991, pp. 51-61 is widely used in view of the accuracy of prediction. In the disclosed method, there is prepared a branch information table which includes the record of what branch was taken for each conditional branch instruction (the record showing the presence of previous branch execution will hereinafter be referred to as branch history information). On the basis of the record, the prediction is made as to whether or not a branch is to be taken at the time of next execution of that conditional branch instruction.
In the method disclosed by the above article, the branch history information includes only the branch execution history record of the last branches up to several. times the amount of the last branches at the most. Therefore, this method has a disadvantage in that it is difficult to predict the result of execution of a conditional branch instruction making an operation in which a branch is taken to a certain branch target address some times and the next instruction is thereafter executed with no branch being taken only one time. Such an operation appears in the most conditional branch instructions with which the judgement is made as to whether or not a loop is to be iterated in a loop portion included in a program. For such a conditional branch instruction, it is difficult to predict a branch at the time of termination of a loop after the iterative execution thereof. Therefore, the prediction in the case of loop termination results in a miss always.